#1孙悟空吃蟠桃
import sys
# import math
#
#
# def check(speed):
#     cost = 0
#     for num in nums:
#         cost += math.ceil(num/speed)
#         if cost > H:
#             return False
#     return True
# nums = list(map(int,input().split()))
# N = len(nums)
# H = int(input())
# if N > H:
#     print(0)
#
# maxSpeed = max(nums)
#
# if N == H:
#     print(maxSpeed)
#
# #二分法
# minSpeed = 1
# ans = maxSpeed
# while minSpeed < maxSpeed:
#     mid = (minSpeed + maxSpeed) >> 1
#     if check(mid):
#         ans = mid
#         maxSpeed = mid - 1
#     else:
#         minSpeed = mid + 1
# print(ans)
# import math

#2电脑病毒感染
# import heapq
# import sys
# n = int(input())
# graph = {}
# m = int(input())
# for i in range(m):
#     u,v,w = map(int,input().split())
#     graph.setdefault(u,[])
#     graph[u].append([v,w])
#
# src = int(input())
#
# visited = [False] * (n+1)
#
# dist = [sys.maxsize] * (n+1)
# dist[src] = 0
#
# pq = []
# heapq.heappush(pq,(dist[src],src))
#
# while len(pq) > 0:
#     u = heapq.heappop(pq)[1]
#     if visited[u]:
#         continue
#
#     visited[u] =  True
#
#     if graph.get(u) is not None:
#         for v,w in graph[u]:
#             newDist = dist[u] + w
#             if dist[v] > newDist:
#                 dist[v] = newDist
#                 heapq.heappush(pq,(dist[v],v))
#
# ans = max(dist[1:])
# print(-1 if ans == sys.maxsize else ans)

#4分词模拟器
# import re
# sentences = list(filter(lambda x: x!= "",re.split(r"[,.;]",input())))
# words = list(filter(lambda x: x!= "",re.split(r"[,.;]",input())))
#
# wordSet = set(words)
#
# ans = []
#
# while len(sentences) > 0:
#     sentence = sentences.pop(0)
#     r = len(sentence)
#     while r > 0:
#         fragment = sentence[0:r]
#         if fragment in wordSet:
#             ans.append(fragment)
#             wordSet.remove(fragment)
#             if r < len(sentence):
#                 sentences.insert(0,sentence[r:])
#             break
#         r -= 1
#     if r == 0:
#         ans.append(sentence[0])
#         if len(sentence) > 1:
#             sentences.insert(0,sentence[1:])
# print(",".join(ans))

#5 跳格子3
# n = int(input())
# scores = list(map(int,input().split()))
# k = int(input())
# length = k + 1
# dp = [0] * n
# dp[0] = scores[0]
# queue = [dp[0]]
# for i in range(1,min(length,n)):
#     dp[i] = queue[0] + scores[i]
#     while len(queue) > 0 and dp[i] > queue[-1]:
#         queue.pop()
#     queue.append(dp[i])
#
# for i in range(length,n):
#     if dp[i-length] == queue[0]:
#         queue.pop(0)
#     dp[i] = queue[0] + scores[i]
#     while len(queue) > 0 and dp[i] > queue[-1]:
#         queue.pop()
#     queue.append(dp[i])
#
# print(dp[n-1])

#6 项目排期
# works = list(map(int,input().split()))
# n = int(input())
# def check(index,buckets,cost):
#     if index == len(works):
#         return True
#     selected = works[index]
#     for i in range(len(buckets)):
#         if i > 0 and buckets[i] == buckets[i - 1]:
#             continue
#         if buckets[i] + selected <= cost:
#             buckets[i] += selected
#             if check(index+1,buckets,cost):
#                 return True
#             buckets[i] -= selected
#     return False
#
# works.sort(reverse=True)
# low = works[0]
# high = sum(works)
# ans = high
# while low <= high:
#     mid = (low + high) >> 1
#     if check(0,[0]*n,mid):
#         ans = mid
#         high = mid-1
#     else:
#         low = mid+1
# print(ans)

#7跳马
# m,n = map(int,input().split())
# grid = [input() for _ in range(m)]
# stepGrid = [[0] * n for _ in range(m)]
#
# #创建所有马都能达到的公共位置
# reach = set()
# for i in range(m):
#     for j in range(n):
#         reach.add(i*n+j)
# #马的偏移量
# offsets = ((1,2),(1,-2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1))
#
# def bfs(sx,sy,k):
#     global  reach
#     #广搜队列
#     queue = [(sx,sy,0)]
#     #记录该马可以访问sx，sy
#     vis = set()
#     vis.add(sx * n + sy)#二维坐标一维化
#
#     while len(queue) > 0 and k>0:
#         newQueue = []
#
#         for x,y,step in queue:
#             for offsetX,offsetY in offsets:
#                 newX = x + offsetX
#                 newY = y + offsetY
#                 pos = newX * n + newY
#                 #新位置越界或者已访问过
#                 if newX < 0 or newX >= m or newY <0 or newY >= n or (pos in vis):
#                     continue
#
#                 newQueue.append((newX,newY,step+1))
#                 stepGrid[newX][newY] += step + 1
#                 vis.add(pos)
#         queue = newQueue
#         k -= 1
#     reach &= vis
#
# for i in range(m):
#     for j in range(n):
#         if grid[i][j] != '.':
#             k = int(grid[i][j])
#             bfs(i,j,k)
#
# if len(reach) == 0:
#     print(-1)
#
# minStep = sys.maxsize
# for pos in reach:
#     x = pos // n
#     y = pos % n
#     minStep = min(minStep,stepGrid[x][y])
#
# print(minStep)

#8字符排列算法
# s,n = input().split()
# n = int(n)
#
# def dfs(cArr,pre,level,used,count):
#     if level == n:
#         count += 1
#         return count
#
#     for i in range(len(cArr)):
#         if used[i]:
#             continue
#         if pre >= 0 and cArr[i] == cArr[pre]:
#             continue
#         if i > 0 and cArr[i] == cArr[i-1] and not used[i-1]:
#             continue
#
#         used[i] = True
#         count = dfs(cArr,i,level+1,used,count)
#         used[i] = False
#
#     return count
#
# if len(s) < n:
#     print(0)
#
# for c in s:
#     if c < 'a' or c > 'z':
#         print(0)
#
# cArr = list(s)
# cArr.sort()
#
# print(dfs(cArr,-1,0,[False]*len(cArr), 0))

#9模拟文件系统管理
# class TreeNode:
#     def __init__(self,curDicName,father):
#         self.curDicName = curDicName
#         self.father = father
#         self.children = {}
#
# class Tree:
#     def __init__(self):
#         #root是根目录，
#         self.root = TreeNode('/',None)
#         self.cur = self.root
#
#     def mkdir(self,dicName):
#         self.cur.children.setdefault(dicName,TreeNode(dicName + '/',self.cur))
#
#     def cd(self,dicName):
#         if dicName == "..":
#             if self.cur.father is not None:
#                 self.cur = self.cur.father
#         else:
#             if self.cur.children.get(dicName) is not None:
#                 self.cur = self.cur.children[dicName]
#
#     def pwd(self):
#         lst = []
#         cur = self.cur
#         while cur is not None:
#             lst.append(cur.curDicName)
#             cur = cur.father
#         lst.reverse()
#         return ''.join(lst)
#
# tree = Tree()
# lastCommandOutput = '/'
# while True:
#     try:
#         line = input()
#         tmp = line.split()
#         cmd_key = tmp[0]
#         if cmd_key == 'pwd':
#             if len(tmp) != 1:
#                 continue
#             lastCommandOutput = tree.pwd()
#         elif cmd_key == 'mkdir' or cmd_key == 'cd':
#             if len(tmp) != 2:
#                 continue
#
#             cmd_val = tmp[1]
#             if not(cmd_val.isalpha() and cmd_val.islower()) and not \
#                     (cmd_key == 'cd' and cmd_val == '..'):
#                 continue
#             if cmd_key  == 'mkdir':
#                 tree.mkdir(cmd_val)
#                 lastCommandOutput = '/'
#             else:
#                 tree.cd(cmd_val)
#                 lastCommandOutput = '/'
#     except:
#         break
# print(lastCommandOutput)

#10智能驾驶
# m,n = map(int,input().split(','))
# matrix = [list(map(int,input().split(','))) for _ in range(m)]
# offsets = ((-1,0),(1,0),(0,-1),(0,1))
# class Node:
#     def __init__(self,x,y):
#         self.x = x
#         self.y = y
#         self.init = 0
#         self.remain = 0
#         self.flag = False #是否加过油
#
# def bfs():
#     if matrix[0][0] == 0 or matrix[m-1][n-1] == 0:
#         return -1
#
#     queue = []
#     src = Node(0,0)
#     if matrix[0][0] == -1:
#         src.init = 0
#         src.remain = 100
#         src.flag = True
#     else:
#         src.init = matrix[0][0]
#         src.remain = 0
#         src.flag = False
#     queue.append(src)
#     dist_init = [[sys.maxsize] * n for _ in range(m)]
#     dist_remain = [[0] * n for _ in range(m)]
#     dist_init[0][0] = src.init
#     dist_remain[0][0] = src.remain
#
#     while len(queue) > 0:
#         cur = queue.pop(0)
#         for offsetX,offsetY in offsets:
#             newX = cur.x + offsetX
#             newY = cur.y + offsetY
#             if newX < 0 or newX >= m or newY < 0 or newY >= n or matrix[newX][newY] == 0:
#                 continue
#             init = cur.init
#             remain = cur.remain
#             flag = cur.flag
#             if matrix[newX][newY] == -1:
#                 remain = 100
#                 flag = True
#             else:
#                 remain -= matrix[newX][newY]
#
#             if remain  < 0:
#                 if flag:
#                     continue
#                 else:
#                     init -= remain
#                     remain = 0
#             if init > 100:
#                 continue
#
#             if init > dist_init[newX][newY]:
#                 continue
#
#             if init < dist_init[newX][newY] or remain > dist_init[newX][newY]:
#                 dist_init[newX][newY] = init
#                 dist_remain[newX][newY] = remain
#
#                 nxt = Node(newX,newY)
#                 nxt.ini = init
#                 nxt.remain = remain
#                 nxt.flag = flag
#
#                 queue.append(nxt)
#
#     if dist_init[m-1][n-1] == sys.maxsize:
#         return -1
#     else:
#         return dist_init[m-1][n-1]
# print(bfs())

#11最大社交距离
# seatNum = int(input())
# seatOrLeave = eval(input())
#
# seatIdx = []
# lastSeatIdx = -1
#
# for info in seatOrLeave:
#     if info < 0:
#         leaveIdx = -info
#         seatIdx.remove(leaveIdx)
#         continue
#
#     if len(seatIdx) == seatNum:
#         lastSeatIdx = -1
#         continue
#     if len(seatIdx) == 0:
#         seatIdx.append(0)
#         lastSeatIdx = 0
#     elif len(seatIdx) == 1:
#         seatIdx.append(seatNum-1)
#         lastSeatIdx = seatNum -1
#     else:
#         bestSeatIdx = -1
#         bestSeatDis = -1
#         left = seatIdx[0]
#         for i in range(1,len(seatIdx)):
#             right = seatIdx[i]
#             dis = right - left + 1
#             if dis > 0:
#                 curSeatDis = dis // 2 - (1 if dis % 2 ==0 else 0)
#                 curSeatIdx = left + curSeatDis + 1
#                 if curSeatDis > bestSeatDis:
#                     bestSeatIdx = curSeatIdx
#                     bestSeatDis = curSeatDis
#             left = right
#         if seatIdx[-1] < seatNum - 1:
#             curSeatDis = seatNum - 1 - seatIdx[-1] - 1
#             curSeatIdx = seatNum - 1
#             if curSeatDis > bestSeatDis:
#                 bestSeatIdx = curSeatIdx
#
#         if bestSeatIdx > 0:
#             seatIdx.append(bestSeatIdx)
#             seatIdx.sort()
#
#         lastSeatIdx = bestSeatIdx
#
# print(lastSeatIdx)

# 12文本数量统计
# text = []
# isSingleOpen = False
# isDoubleOpen = False
# while True:
#     try:
#         s= input()
#         for i in range(len(s)):
#             c = s[i]
#             if i == 0 or s[i-1] != '\\':
#                 if c == '\'':
#                     isSingleOpen = not isSingleOpen
#                 elif c == '"':
#                     isDoubleOpen = not isDoubleOpen
#             if isSingleOpen or isDoubleOpen:
#                 continue
#             if c == '-' and i+1 < len(s) and s[i+1] == '-':
#                 break
#             if c != ' ' and c!= '\t':
#                 text.append(c)
#     except:
#         break
# text.append(';')
# ans = 0
# last = -1
# for i in range(len(text)):
#     if text[i] == ';':
#         if i -last > 1:
#             ans += 1
#         last = i
# print(ans)


#13找单词
# n = int(input())
# arr = [list(map(int,input().split(','))) for _ in range(n)]
# tar = input()
# offset = ((0,1),(0,-1),(1,0),(-1,0))
# used = [[False] * n for _ in range(n)]
# path = []
# def dfs(i,j,k):
#     if i < 0 or i > n or j < 0 or j > n or arr[i][j] != tar[k] or used[i][j]:
#         return False
#     path.append(f'{i},{j}')
#     if len(path) == len(tar):
#         return True
#     used[i][j] = True
#
#     res = dfs(i-1,j,k+1) or dfs(i+1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1)
#     if not res:
#         used[i][j] = False
#         path.pop()
#     return res
#
# for i in range(n):
#     for j in range(j):
#         if dfs(i,j,0):
#             print(','.join(path))
#             exit(0)
# print('N')

#14字符串化繁为简
# class UnionFindSet:
#     def __init__(self,n):
#         self.fa = [i for i in range(n)]
#     def find(self,x):
#         if x != self.fa[x]:
#             self.fa[x] = self.find(self.fa[x])
#             return self.fa[x]
#         return x
#
#     def union(self,x,y):
#         x_fa = self.find(x)
#         y_fa = self.find(y)
#         if x_fa < y_fa:
#             self.fa[y_fa] = x_fa
#         else:
#             self.fa[x_fa] = y_fa
#
# s = input()
# #主体
# cArr = []
# #等效
# eq = []
# ufs = UnionFindSet(128)
# occurs = set()
# isOpen = False
# for c in s:
#     if c == '(':
#         isOpen = True
#     elif c == ')':
#         #括号间等效传递
#         isOpen = False
#         if len(eq) == 0:
#             continue
#         for letter in eq:
#             upper = letter - 32
#             lower = letter + 32
#
#             if lower in occurs:
#                 ufs.union(letter,lower)
#
#             if upper in occurs:
#                 ufs.union(letter,upper)
#         #括号内等效传递
#         base = eq[0]
#         for letter in eq:
#             ufs.union(letter,base)
#             occurs.add(letter)
#         eq.clear()
#
#     elif isOpen:
#         eq.append(ord(c))
#     else:
#         cArr.append(ord(c))
#
# for i in range(128):
#     ch = i
#     fa = ufs.find(i)
#
#     for j in range(len(cArr)):
#         if cArr[j] == ch:
#             cArr[j] = fa
#
# res = ''.join(map(lambda x:chr(x),cArr))
#
# if len(res) == 0:
#     print('0')
# else:
#     print(res)

#15软盘文件拷贝优化
# import math
# n = int(input())
# arr = [int(input()) for _ in range(n)]
#
# bag = 1474560 // 512
# dp = [[0] * (bag+1) for _ in range(n+1)]
# for i in range(1,n+1):
#     weight = math.ceil(arr[i-1]/512)
#     worth = arr[i-1]
#     for j in range(bag+1):
#         if weight > j:
#             dp[i][j] = dp[i-1][j]
#         else:
#             dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight] + worth)
#
# print(dp[n][bag])

#16周末爬山
# m,n,k  = list(map(int,input().split()))
# matrix = [list(map(int,input().split()))for _ in range(m)]
# maxHeight = matrix[0][0]
# minstep = 0
# offset = ((0,1),(0.-1),(1,0),(-1,0))
# def bfs():
#     global minstep,maxHeight
#     queue = []
#     visted = [[False] * n for _ in range(m)]
#     queue.append((0,0))
#     visted[0][0] = True
#     step = 0
#     while len(queue) > 0:
#         newQueue = []
#         step += 1
#         for x,y in queue:
#             lastHeight = matrix[x][y]
#             for offsetX,offsetY in offset:
#                 newX = x + offsetX
#                 newY = y + offsetY
#                 if newX < 0 or newY < 0 or newX > m-1 or newY > n-1:
#                     continue
#                 curHeight = matrix[newX][newY]
#                 if abs(curHeight - lastHeight) <= k:
#                     visted[newX][newY] = True
#
#                     if curHeight > maxHeight or (curHeight == maxHeight and step < minstep):
#                         maxHeight = curHeight
#                         minstep = step
#
#                     newQueue.append((newX,newY))
#         queue = newQueue
#
# bfs()
# if minstep == 0:
#     print('0 0')
# else:
#     print(f'{maxHeight} {minstep}')

#17数字游戏
# def isExist(nums, m):
#     remain = set()
#     remain.add(0)
#     total = 0
#     for num in nums:
#         total += num
#         if total % m in remain:
#             return 1
#         else:
#             remain.add(total % m)
#     return 0
# while True:
#     try:
#         n, m = map(int, input().split())
#         nums = list(map(int, input().split()))
#         print(isExist(nums, m))
#     except:
#         break

#18树结构查询
# n = int(input())
# tree = {}
# for _ in range(n):
#     ch,fa = input().split()
#     tree.setdefault(fa,set())
#     tree[fa].add(ch)
# target = input()
#
# if tree.get(target) is None:
#     print("")
#
# ans = []
# queue = list(tree[target])
# while len(queue) > 0:
#     node = queue.pop(0)
#     ans.append(node)
#     if tree.get(node) is not None:
#         queue.extend(list(tree[node]))
# print('\n'.join(sorted(ans)))

#19矩阵中连续男生最大数量
# n,m = map(int,input().split(','))
# matrix = [input().split(',')for _ in range(n)]
#
# ans = 0
# offsets = ((0,1),(1,0),(1,1),(1,-1))
# for i in range(n):
#     for j in range(m):
#         if matrix[n][m] == 'M':
#             for offset in offsets:
#                 oldI = i - offset[0]
#                 oldJ = j - offset[1]
#
#                 if n > oldI >= 0 and m > oldJ >= 0 and matrix[oldI][oldJ] == 'M':
#                     continue
#                 length = 1
#                 newI = i + offset[0]
#                 newJ = j + offset[1]
#
#                 while n > newI >= 0 and m > newJ >= 0 and matrix[newI][newJ] == 'M':
#                     length += 1
#                     newI += offset[0]
#                     newJ += offset[1]
#                 ans = max(ans,length)
# print(ans)

#20连续交替方波
# import re
# s = input()+'0'
# ans = ''
# reg = re.compile('^(01)+0$')
# i,j = 0,1
# while j < len(s):
#     if s[j-1] == '0' and s[j] == '0':
#         sub = s[i:j]
#         if reg.match(sub) and len(sub) > len(ans):
#             ans = sub
#         i = j
#     j += 1
#
# print('-1' if len(ans) == 0 else ans)

#21网络信号计算
# m,n = map(int,input().split())
# nums = list(map(int,input().split()))
# tx,ty = map(int,input().split())
# queue = []
# matrix = [ [0] * n for _ in range(m)]
# for i in range(m):
#     for j in range(n):
#         matrix[i][j] = nums[i * n + j]
#         if nums[i * n + j] > 0:
#             queue.append((i,j))
#
# offsets = ((-1,0),(1,0),(0,-1),(0,1))
# while len(queue) > 0:
#     size = len(queue)
#     for _ in range(size):
#         x,y = queue.pop(0)
#         for offset in offsets:
#             newX = x + offset[0]
#             newY = y + offset[1]
#             if 0 <= newX < m and 0 <= newY < n and matrix[newX][newY] == 0:
#                 matrix[newX][newY] = matrix[x][y] - 1
#                 if matrix[newX][newY] > 0:
#                     queue.append((newX,newY))
# print(matrix[tx][ty])

#22最长双字符子串
# ex = ord(input())
# s = input()
#
# count = [0] * 128
# l = 0
# r = 0
# ans = 0
# while r < len(s):
#     add_c = ord(s[r])
#     if ex == add_c:
#         ans = max(ans,r-l)
#         r += 1
#         l = r
#         count = [0] * 128
#     else:
#         count[add_c] += 1
#         if count[add_c] > 2:
#             ans = max(ans,r-l)
#         while count[add_c] > 2:
#             remove_c = ord(s[l])
#             count[remove_c] -= 1
#             l += 1
#         r+=1
# ans = max(ans,r-l)
# print(ans)

#23国庆云短信优惠
# n = int(input())
# weight = list(map(int,input().split()))
#
# dp = [0] * (n+1)
# for i in range(len(weight)):
#     for j in range(i+1,n+1):
#         dp[j] = max(dp[j],dp[j - 1 - i]+weight[i])
# print(dp[n])


#24狼羊过河

# def dfs(sheep,wolf,boat,oppo_sheep,oppo_wolf,count,ans):
#     if sheep == 0 and wolf == 0:
#         ans.append(count)
#         return
#     if sheep + wolf <= boat:
#         ans.append(count+1)
#         return
#     for i in range(min(boat,sheep)+1):
#         for j in range(min(boat,sheep)+1):
#             #空运
#             if i + j == 0:
#                 continue
#             if i + j > boat:
#                 break#超载
#             #本岸羊<= 本岸狼 说明狼运少了
#             if sheep - i <= wolf - j and sheep -i != 0:
#                 continue
#             #对岸羊 <= 对岸狼，说明狼运多了
#             if oppo_sheep + i <= oppo_wolf + j and oppo_sheep + i != 0:
#                 break
#             #对岸没羊，但对岸狼已超过船载量，下次即使整船运羊，也无法保证对岸羊>对岸狼
#             if oppo_sheep + i == 0 and oppo_wolf + j >= boat:
#                 break
#             dfs(sheep-i,wolf-j,boat,oppo_sheep+i, oppo_wolf+j, count+1, ans)
#
# m,n,x = map(int,input().split())
# ans = []
# dfs(m,n,x,0,0,0,ans)
# if len(ans) > 0:
#     print(min(ans))
# else:
#     exit()

#25光伏电站选址
# r,c,s,minV = map(int,input().split())
# matrix = [list( map(int,input().split())) for _ in range(r)]
# preSum = [[0 for _ in range(c+1)] for _ in range(r+1)]
# for i in range(1,r+1):
#     for j in range(1,c+1):
#         preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
# ans = 0
# for i in range(s,r+1):
#     for j in range(s,c+1):
#         square = preSum[i][j] - (preSum[i-s][j]+preSum[i][j-s]) + preSum[i-s][j-s]
#         if square > minV:
#             ans+=1
# print(ans)

#26充电设备组合
# n = int(input())
# ps = list(map(int,input().split()))
# p_max = int(input())
# dp = [0] * (p_max + 1)
# for i in range(n):
#     p = ps[i]
#     for j in range(p_max,p-1,-1):
#         dp[j] = max(dp[j],dp[j-p]+p)
# print(dp[p_max])

#27转骰子
# class Rotate:
#     def __init__(self):
#         self.left = 1
#         self.right = 2
#         self.front = 3
#         self.back = 4
#         self.top = 5
#         self.bottom = 6
#     def turnL(self):
#         self.top,self.right,self.bottom,self.left = self.right,self.bottom,self.left,self.top
#
#     def __str__(self):
#         return f"{self.left}{self.right}"
# directs = input()
# dice = Rotate()
# for direct in directs:
#     if direct == 'L':
#         dice.turnL()
# print(str(dice))

#28吃火锅
# n,m = map(int,input().split())
# suit = []
# for _ in range(n):
#     x,y = map(int,input().split())
#     suit.append(x+y)
# suit.sort()
# count = 1
# pre = 0
# for i in range(1,len(suit)):
#     if suit[i] > suit[pre] + m:
#         count+=1
#         pre = i
# print(count)

#29最大值
# import re
# import functools
# def cmp(a,b):
#     s1 = b + a
#     s2 = a + b
#     return 1 if s1 >= s2 else -1
# nums = input().split()
# nums.sort(key=functools.cmp_to_key(cmp))
# print(re.sub('^0+','0',''.join(nums)))

#30疫情扩散计算
# s = list(map(int,input().split(',')))
# n = int(math.sqrt(len(s)))
# matrix = [[0 for _ in range(n)] for _ in range(n)]
# queue = []
# for i in range(n):
#     for j in range(n):
#         matrix[i][j] = s[i*n + j]
#         if matrix[i][j] == 1:
#             queue.append([i,j])
# if len(queue) == 0 or len(queue) == len(s):
#     print(-1)
#     exit(0)
#
# healthy = len(s) - len(queue)
# offsets = ((-1,0),(1,0),(0,-1),(0,1))
# day = 0
# while len(queue) > 0 and healthy > 0:
#     size = len(queue)
#     for i in range(size):
#         x,y = queue.pop(0)
#         for offsetX,offsetY in offsets:
#             newX = x + offsetX
#             newY = y + offsetY
#             if 0<= newX < n and 0 <= newY < n and matrix[newX][newY] == 0:
#                 matrix[newX][newY] = 1
#                 healthy -= 1
#                 queue.append([newX,newY])
#     day+=1
# print(day)

#31服务器广播
# class UnionFindSet:
#     def __init__(self,n):
#         self.fa = [i for i in range(n)]
#         self.count = n
#     def find(self,x):
#         if x!= self.fa[x]:
#             self.fa[x] = self.find(self.fa[x])
#             return self.fa[x]
#         return x
#     def union(self,x,y):
#         x_fa = self.find(x)
#         y_fa = self.find(y)
#         if x_fa != y_fa:
#             self.fa[y_fa] = x_fa
#             self.count -= 1
#
# matrix = []
# while True:
#     try:
#         matrix.append(input().split())
#     except:
#         break
# n = len(matrix)
# ufs = UnionFindSet(n)
# for i in range(n):
#     for j in range(i+1,n):
#         if matrix[i][j] == '1':
#             ufs.union(i,j)
# print(ufs.count)

#32九宫格按键输入
# dic = (' ',',.','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz')
# isNumNode = True
# delay_num = -1
# delay_idx = -1
# res = []
# def interrupt(c):
#     global delay_num
#     global delay_idx
#     if delay_num != -1:
#         res.append(dic[delay_num][delay_idx])
#     if c == '#' or c == '/':
#         delay_num = -1
#         delay_idx = -1
#     else:
#         delay_num = int(c)
#         delay_idx = 0
# s = input() + '/'
# for c in s:
#     if c == '#':
#         isNumNode = not isNumNode
#     if c == '#' or c == '/':
#         interrupt(c)
#     elif isNumNode:
#         res.append(c)
#     elif int(c) == delay_num:
#         delay_idx += 1
#         delay_idx %= len(dic[delay_num])
#     else:
#         interrupt(c)
# print(''.join(res))

#33字母组合
# s = input()
# de = input()
# dic = ['abc','def','ghi','jkl','mno','pqr','st','uv','wx','yz']
# res = []
#
# def dfs(level,path):
#     if level == len(s):
#         pathSet = set(path)
#
#         for c in de:
#             if c not in pathSet:
#                 res.append(''.join(path))
#                 return
#         return
#
#     num = ord(s[level]) - ord('0')
#     letters = dic[num]
#
#     for letter in letters:
#         path.append(letter)
#         dfs(level+1,path)
#         path.pop()
# print(dfs(0,[]))


#34机器人活动范围
# m,n = map(int,input().split())
# matrix = [list(map(int,input().split())) for _ in range(m)]
# offsets = ((0,1),(0,-1),(1,0),(-1,0))
# visited = [[False] * n for _ in range(m)]
#
# def dfs(i,j,count):
#     for offset in offsets:
#         newX = i + offset[0]
#         newY = j + offset[1]
#         if m > newX >= 0 and n > newY >= 0 and abs(matrix[newX][newY] - matrix[i][j]) <= 1 and not visited[newX][newY]:
#             visited[newX][newY] = True
#             count = dfs(newX,newY,count+1)
#     return count
#
# ans = 0
# for i in range(m):
#     for j in range(n):
#         if not visited[i][j]:
#             visited[i][j] = True
#             ans = max(ans,dfs(i,j,1))
# print(ans)

#35最大可观看演出
# n = int(input())
# if n < 1 or n > 1000:
#     exit()
# times = []
# for _ in range(n):
#     t,l = map(int,input().split())
#     if t < 0 or t > 1400 or l <= 0 or l > 180:
#         exit()
#     times.append([t,t+l])
# times.sort(key = lambda x : x[1])
# count = 1
# last_end= times[0][1]
# for i in range(1,n):
#     start,end = times[i]
#     if start - last_end >= 15:
#         count += 1
#         last_end = end
#
# print(count)

#36数字排列
# nums = list(map(int,input().split(',')))
# mapping = {2:5,5:2,6:9,9:6}
# def dfs(vis,path,res):
#     if len(path) > 0:
#         res.append(int(''.join(map(str,path))))
#     if len(path) == len(nums):
#         return
#     for i in range(len(nums)):
#         if vis[i]:
#             continue
#         vis[i] = True
#         path.append(i)
#         dfs(vis,path,res)
#         path.pop()
#         if nums[i] in mapping:
#             path.append(mapping[nums[i]])
#             dfs(vis, path, res)
#             path.pop()
#
#         vis[i] = False
#
# for num in nums:
#     if num < 1 or num >9 :
#         exit()
# setNums = set(nums)
# if len(setNums) != 4:
#     exit()
# if 2 in setNums and 5 in setNums:
#     exit()
# vis = [False] * len(nums)
# path = []
# res = []
# dfs(vis,path,res)
# res.sort()
# n = min(max(nums),len(res))
# print(res[n-1])

#37melon的难题
# n = int(input())
# nums = list(map(int,input().split()))
# if sum(nums) % 2 != 0:
#     exit()
# else:
#     bag = sum(nums) // 2 #负重
#     dp = [[0] * (bag+1) for _ in range(n+1)]
#     for i in range(bag+1):
#         dp[0][i] = n
#     dp[0][0] = 0
#     for i in range(1,n+1):
#         num = nums[i-1]
#         for j in range(1,bag+1):
#             if j < num:
#                 dp[i][j] = dp[i-1][j]
#             else:
#                 dp[i][j] = max(dp[i-1][j],dp[i-1][j-num]+1)
#
#     if dp[n][bag] == n:
#         exit()
#     else:
#         print(min(n-dp[n][bag],dp[n][bag]))

#38打印任务排序
# from collections import deque
# priorities = list(map(int,input().split(',')))
# n = len(priorities)
# queue = deque()
# for i in range(n):
#     queue.append((priorities[i],i))
# result = [0] * n
# priorities.sort(reverse=True)
# printIndex = 0
# while queue:
#     priority,index = queue.popleft()
#     if priority == priorities[printIndex]:
#         result[index] = printIndex
#         printIndex += 1
#     else:
#         queue.append((priority,index))

#39特殊加密
# n = int(input())
# datas = list(map(int,input().split()))
# m = int(input())
# secrets = []
# starts = []
# for i in range(m):
#     secrets.append(list(map(int,input().split())))
#     for j in range(m):
#         if secrets[i][j] == 0:
#             starts.append((i,j))
# offsets = ((0,1),(0,-1),(1,0),(-1,0))
# def dfs(x,y,index,path,used):
#     if index == n:
#         return True
#     for offsetx,offsety in offsets:
#         newX = x + offsetx
#         newY = y + offsety
#         if newX < 0 or newX >= m or newY < 0 or newY >= m or used[newX][newY] or secrets[newX][newY] != datas[index]:
#             continue
#         path.append(f'{newX} {newY}')
#         used[newX][newY] = True
#         if dfs(newX,newY,index+1,path,used):
#             return True
#         used[newX][newY] = False
#         path.pop()
#     return False
#
# for x,y in starts:
#     used = [[False] * m for _ in range(m)]
#     used[x][y] = True
#     path = [f"{x} {y}"]
#
#     if dfs(x,y,1,path,used):
#         print( ' '.join(path))
#     else:
#         print('error')

#40矩阵匹配
# import sys
# # 输入获取
# n, m, k = map(int, input().split())
# matrix = [list(map(int, input().split())) for _ in range(n)]
#
# def dfs(i, kth, match, vis):
#     # 行号 i 发起了配对请求
#     # 遍历每一个列号j
#     for j in range(m):
#         # 如果当前列号j未被增广路探索过 && 当前列j行i可以配对（如果行列号位置(i,j)对应矩阵元素值小于等于kth（第K大值），则可以配对）
#         if not vis[j] and matrix[i][j] <= kth:
#             vis[j] = True
#
#             # 如果对应列号j未配对，或者，已配对但是配对的行号match[j]可以找到其他列号重新配对
#             if match[j] == -1 or dfs(match[j], kth, match, vis):
#                 # 则当前行号i 和 列号j 可以配对
#                 match[j] = i
#                 return True
#     return False
#
#
# def check(kth):
#     # 利用二分图最大匹配来求解，小于等于kth（第K大值）的元素个数（即二分图最大匹配）
#     smallerCount = 0
#     # 记录每个列号的匹配成功的行号
#     # 初始时每个列号都处于未配对状态，此时将列号配对的行号赋值为-1
#     match = [-1] * m
#     # 遍历行号，每个行号对互相心仪的列号发起配对请求
#     for i in range(n):
#         # 记录增广路访问过的列号
#         vis = [False] * m
#         if dfs(i, kth, match, vis):
#             smallerCount += 1
#     return smallerCount >= n - k + 1
# # 算法入口
# def getResult():
#     low = 1
#     high = -sys.maxsize
#     for i in range(n):
#         for j in range(m):
#             high = max(high, matrix[i][j])
#
#     # 二分枚举第K大值
#     while low <= high:
#         # mid就是被枚举出来的N个数中的第K大值
#         mid = (low + high) >> 1
#         # 检查mid作为N个数中第K大值时，是否存在N-K+1个<=它的值
#         if check(mid):
#             high = mid - 1
#         else:
#             low = mid + 1
#     return low


#41最大可处理任务
# import  heapq
# n = int(input())
#
# ranges = [list(map(int,input().split())) for _ in range(n)]
#
# ranges.sort(key = lambda  x: -x[1])
# print(ranges)
# pq = []
# pq_end = sys.maxsize
# count  = 0
# for start,end in ranges:
#     while len(pq) > 0 and end < pq_end:
#         a = -heapq.heappop(pq)
#         print(a)
#         if a <= pq_end:
#             count += 1
#             pq_end -= 1
#     heapq.heappush(pq,-start)
#     pq_end = end
# while len(pq) > 0:
#     if -heapq.heappop(pq) <= pq_end:
#         count +=1
#         pq_end -= 1
# print(count)

#42亚索报文解码
# s = input()
# stack = []
# next_k = 0
# cur_encoding_string = ''
# for c in s:
#     if c.isdigit():
#         next_k = next_k * 10 + int(c)
#     elif c == '[':
#         stack.append((next_k,cur_encoding_string))
#         next_k = 0
#         cur_encoding_string = ''
#     elif c == ']':
#         cur_k,pre_encode_string = stack.pop()
#         cur_encoding_string = pre_encode_string + cur_encoding_string * cur_k
#     else:
#         cur_encoding_string += c
# print(cur_encoding_string)

#43宜居星球改造
# def bfs():
#     row = len(matrix)
#     col = len(matrix[0])
#     queue = []
#     need = 0
#     for i in range(row):
#         for j in range(col):
#             if matrix[i][j] == 'YES':
#                 queue.append([i,j])
#             elif matrix[i][j] == 'NO':
#                 need += 1
#     if len(queue) == 0:
#         return -1
#     if len(queue) == row * col:
#         return 0
#     day = 0
#     offsets = ((0,1),(0,-1),(1,0),(-1,0))
#     while len(queue) > 0 and need >0:
#         size = len(queue)
#         for _ in range(size):
#             x,y = queue.pop(0)
#             for offset in offsets:
#                 newX = x+ offset[0]
#                 newY = y + offset[1]
#                 if row > newX >= 0 and col > newY >= 0 and matrix[newX][newY] == 'NO':
#                     matrix[newX][newY] = 'YES'
#                     queue.append([newX,newY])
#                     need -= 1
#         day += 1
#     if need == 0:
#         return day
#     else:
#         return -1
# matrix = []
# N = 0
# while N < 4:
#     try:
#         matrix.append(input().split())
#         N+=1
#     except:
#         break

#44篮球游戏
# ipts = list(map(map(int,input().split(','))))
# opts = list(map(map(int,input().split(','))))
# def solution():
#     queue = []
#     index = 0
#     res = []
#     for ipt in ipts:
#         queue.append(ipt)
#         while len(queue) > 0 and index < len(opts):
#             left = queue[0]
#             right = queue[-1]
#             if left == opts[index]:
#                 res.append('L')
#                 queue.pop(0)
#                 index += 1
#             elif right == opts[index]:
#                 res.append('R')
#                 queue.pop()
#                 index += 1
#             else:
#                 break
#     if index != len(opts):
#         return 'NO'
#     else:
#         return ''.join(map(str,res))
#46 矩形绘制
# 输入获取
# n = int(input())
# rects = [input().split() for _ in range(n)]
# for rect in rects:
#     rect[1] = int(rect[1])
#     rect[2] = int(rect[2])
#     rect[3] = int(rect[3])
#     rect[4] = int(rect[4])
# # 区间差集
# def getDiff(draw_lines, erase_line):
#     lines = []
#
#     s1, e1 = erase_line
#     for s, e in draw_lines:
#         if s1 >= e or s >= e1:
#             lines.append((s, e))
#         elif s < s1 and e1 < e:
#             lines.append((s, s1))
#             lines.append((e1, e))
#         elif s <= s1 < e <= e1:
#             lines.append((s, s1))
#         elif s1 <= s < e1 <= e:
#             lines.append((e1, e))
#
#     return lines

# 区间并集长度
# def getUnionLen(lines):
#     # 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同, 则按照结束位置降序，这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
#     lines.sort(key=lambda line: (line[0], -line[1]))
#     # 记录lines多个区间，求长度之和，（重叠部分只计算一次）
#     height = 0
#     # 题目说坐标范围 [-100, 100], 因此对应 [?, -101] 的区间必然不会和任何区间相交
#     last_end = -101
#     # 如果 last_end >= end, 则当前区间被上一个区间完全覆盖，因此可以跳过
#     for start, end in lines:
#         if last_end < end:
#             # 则当前区间的不重叠部分是 [max(start, last_end), end]
#             height += end - max(start, last_end)
#             # 更新last_end
#             last_end = end
#     return height
# def solution():
#     # 统计所有矩形的左边边、右边边所在位置的x坐标
#     listX = []
#     for op, x1, y1, x2, y2 in rects:
#         listX.append(x1)  # 矩形左边边x坐标位置
#         listX.append(x2)  # 矩形右边边x坐标位置
#     # 所有x坐标升序（每个x视为一条扫描线）
#     listX.sort()
#     # 记录所有矩形并集面积
#     ans = 0
#     for i in range(1, len(listX)):
#         # 前一个扫描线x坐标
#         preX = listX[i - 1]
#         # 当前扫描线x坐标
#         curX = listX[i]
#         # 相邻两个扫描线的距离
#         width = curX - preX
#         # 距离为0, 则跳过
#         if width == 0:
#             continue
#         # 处于水平方向 [preX, curX] 范围，对应的垂直方向上 绘制矩形 的区间
#         draw_lines = []
#         for op, x1, y1, x2, y2 in rects:
#             if x1 <= preX and curX <= x2:
#                 if op == 'd':
#                     draw_lines.append((y2, y1))
#                 elif op == 'e':
#                     draw_lines = getDiff(draw_lines, (y2, y1))
#         # 当前扫描线扫描到的面积为 width * height
#         ans += width * getUnionLen(draw_lines)
#     return ans

#46推荐多样性
# 输入获取
# n = int(input())
# k = int(input())
# lists = []
# while True:
#     try:
#         lists.append(list(map(int, input().split())))
#     except:
#         break
# # 算法入口
# def getResult():
#     # 窗口矩阵，k行n列，每一列对应一个窗口，这里将二维矩阵一维化，方便后面赋值
#     windows = [0] * (k * n)
#     # 窗口矩阵中正在赋值的索引位置
#     idx = 0
#     # 正在从第level个列表中取值
#     level = 0
#     # 当窗口矩阵填满后，结束循环
#     while idx < len(windows):
#         # 当前轮次是否发生了"借"动作
#         flag = False
#         # 从第level个列表中取前n个元素
#         for _ in range(n):
#             windows[idx] = lists[level].pop(0)
#             idx += 1
#             # 如果第level个列表没有元素了，则继续切到下一个列表中"借"
#             if len(lists[level]) == 0 and len(lists) > 1:
#                 lists.pop(level)  # 删除空列表
#                 level %= len(lists)  # 防止越界
#                 flag = True  # 发生了"借"动作
#         #  如果没有发生"借"动作，则需要切到下一行
#         if not flag:
#             level = (level + 1) % len(lists)  # 防止越界
#     ans = []
#     # 遍历列号
#     for j in range(n):
#         for i in range(k):
#             ans.append(windows[i * n + j])
#     return " ".join(map(str, ans))

#47 任务最优调度
# # 输入获取
# tasks = list(map(int, input().split(",")))
# n = int(input())
# # 算法入口
# def getResult():
#     cnts = {}
#     for task in tasks:
#         cnts[task] = cnts.get(task, 0) + 1
#     # k表示: 最多任务的数量
#     # 比如2, 2, 2, 3， 其中任务2数量最多，有3个，则k = 3
#     k = max(cnts.values())
#     # p表示: 数量为k的任务个数
#     # 比如2, 2, 2, 3, 3, 3, 4， 其中数量为3的任务有2个，分别是任务2，任务3，则p = 2
#     p = 0
#     for task in cnts:
#         if cnts[task] == k:
#             p += 1
#     return max((k - 1) * (n + 1) + p, len(tasks))

#48编码能力提升
# 输入获取
# times = list(map(int, input().split(",")))
# m = int(input())
# def check(t):
#     # 今天总耗时
#     sum_cost = 0
#     # 今天耗时最多的题目的耗时
#     max_cost = 0
#     # 今天是否可以申请帮助
#     canHelp = True
#     # 第几天
#     day = 1
#     i = 0
#     while i < len(times):
#         sum_cost += times[i]
#         max_cost = max(max_cost, times[i])
#         if sum_cost > t:
#             # 如果做完times[i]，总耗时超过了t
#             if canHelp:
#                 # 如果可以申请帮助，那么就看耗时最长的题目的答案
#                 sum_cost -= max_cost
#                 # 今天申请帮助的机会用完了
#                 canHelp = False
#                 # 下面继续做下一题
#                 i += 1
#             else:
#                 # 如果不能申请帮助，则今天做不了times[i]题目，只能放到明天做
#                 # 进入明天
#                 day += 1
#                 # 重置总耗时，最大耗时题目，以及申请帮助机会
#                 sum_cost = 0
#                 max_cost = 0
#                 canHelp = True
#         else:
#             # 如果做完times[i]，总耗时没有超过t，则继续做下面的题目
#             i += 1
#     return day <= m
# # 算法入口
# def getResult():
#     # T的初始取值范围
#     low = 0
#     high = sum(times) - max(times)
#     # 二分
#     while low <= high:
#         # 取中间值尝试
#         mid = (low + high) >> 1
#
#         if check(mid):
#             high = mid - 1
#         else:
#             low = mid + 1
#     return low

#49最佳植树距离
# 输入获取
# n = int(input())
# positions = list(map(int, input().split()))
# m = int(input())
# def check(minDis):
#     count = 1
#     last = 0
#     for cur in range(1, n):
#         if positions[cur] - positions[last] >= minDis:
#             count += 1
#             last = cur
#     return count >= m
# # 算法入口
# def solution():
#     positions.sort()
#     low = 1
#     high = positions[-1] - positions[0]
#     ans = 0
#     while low <= high:
#         mid = (low + high) >> 1
#         if check(mid):
#             ans = mid
#             low = mid + 1
#         else:
#             high = mid - 1
#     return ans
